package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.TreeNode;

public class _053_剑指OfferII二叉搜索树中的中序后继 {

    // 根据二叉搜索树的性质获取, 贪心获取
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode res = null;
        while (root != null) {
            if (root.val > p.val) {
                res = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return res;
    }


    private TreeNode resNode;

    private TreeNode curNode;

    public TreeNode inorderSuccessor1(TreeNode root, TreeNode p) {

        dfs(root, p);

        return resNode;
    }

    private void dfs(TreeNode root, TreeNode p) {
        if (root == null) return;

        dfs(root.left, p);
        if (curNode != null && resNode != null) {
            resNode = root;
            return;
        }
        if (root.val == p.val) {
            curNode = root;
        }
        dfs(root.right, p);
    }


}
